package com.zhaofan.other;
//给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
//
// 有效字符串需满足：
//
//
// 左括号必须用相同类型的右括号闭合。
// 左括号必须以正确的顺序闭合。
//
//
//
//
// 示例 1：
//
//
//输入：s = "()"
//输出：true
//
//
// 示例 2：
//
//
//输入：s = "()[]{}"
//输出：true
//
//
// 示例 3：
//
//
//输入：s = "(]"
//输出：false
//
//
// 示例 4：
//
//
//输入：s = "([)]"
//输出：false
//
//
// 示例 5：
//
//
//输入：s = "{[]}"
//输出：true
//
//
//
// 提示：
//
//
// 1 <= s.length <= 10⁴
// s 仅由括号 '()[]{}' 组成
//
// Related Topics 栈 字符串 👍 2651 👎 0


import org.junit.Assert;
import org.junit.Test;

import java.util.HashMap;
import java.util.LinkedList;

public class No20 {

    @Test
    public void test(){
        String str="(]";
        boolean b = isValid(str);
        Assert.assertTrue(b);
    }

    /**
     * 高途面试，没有一次做出来
     * 有感而发，面试的时候千万不能因为紧张而忘记思考，面对算法题要多模拟临界条件
     *
     * 今天得知有几个同事因为延迟转正而提离职，心里也不是滋味
     * 加强自身，
     * 靡不有初，鲜克有终
     * ps.定一个目标，等做到了美团面试的那一道题，就撤！就撤！就撤！
     */
    public  boolean isValid(String s) {
        HashMap<Character, Character> map = new HashMap<>(3);
        map.put('}','{');
        map.put(')','(');
        map.put(']','[');
        if(s==null||s.length()==0||s.length()%2!=0) return false;
        LinkedList<Character> stack = new LinkedList<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if(!map.containsKey(c)){
                stack.push(c);
            }else{
                Character c1 = stack.poll();
                if(c1!=map.get(c)) return false;
            }
        }
        if(!stack.isEmpty()) return false;
        return true;
    }
}
